1. Field of the Invention
This invention relates to memory management, and more specifically to systems and methods for collecting garbage in memory.
2. Background of the Invention
In an object-oriented managed runtime, such as the Java Virtual Machine (JVM), Microsoft Common Language Runtime (CLR), or Smalltalk runtime, the primary memory resource is a garbage-collected object heap. The object heap provides memory for objects, each of which is an instance of a class. All managed runtimes support object garbage collection. Garbage collection attempts to reclaim garbage, or memory occupied by objects that are no longer in use by programs.
Various different approaches exist for collecting garbage on the object heap, each with various advantages and disadvantages. For example, global garbage collectors collect garbage from the entire object heap, whereas local garbage collectors (e.g., region-based garbage collectors) collect garbage only from a portion of the object heap. Global garbage collectors are typically standard mark-sweep (and optionally compact) collectors. Local garbage collectors are typically copy collectors, although mark-sweep collectors may also be used.
A copy collector works, in part, by copying live objects from one space (i.e., the source space) to another space (i.e., the destination space, also referred to as the survivor space). This type of collector has the advantage that it can mark and copy live objects in a single pass over the heap. It can also achieve good locality of objects in the survivor space. One disadvantage of this type of collector is that it requires extra memory for the survivor space. The amount of memory needed for the survivor space can be difficult to predict. When the survivor space is insufficient (i.e., there are more live objects than can be copied to the survivor space), the copy process aborts. Such an abort condition requires a recovery to update stale references and bring the heap back to a consistent state.
In a mark-sweep collector, a bit is typically provided for each object in memory. Each bit is cleared prior to a garbage collection cycle. During the garbage collection cycle, an object graph is traversed, starting with root objects, until all live objects are found. The bit for each live object is set (or “marked”) to indicate that the object is in use. Once each live object is marked, each object in memory may be examined again. Objects with bits cleared are not reachable by any program or data, allowing their memory to be freed. The advantage of a mark-sweep collector is that it is slightly faster than a copy collector since it doesn't write to the heap. If a compactor is invoked, which may slide objects toward a low or high address of the source space, there is typically no need for a separate survivor space. Thus, a mark-sweep-compact collector is free from the abort problems associated with a copy collector—the mark-sweep-compact is guaranteed to complete successfully. The disadvantage is that, in the event the compactor is invoked frequently, the mark and compact processes together require two passes through the live objects.
In the event a copy collector aborts the copy of an object due to insufficient space in the destination space, recovering can be quite expensive. For example, such an event may require an explicit pass through the heap to fix stale heap references. If accurate mark bit information is required, a marking operation may also need to be performed on the entire collection set. A collector with an explicit fix-up phase and complete mark phase, when an abort occurs, is typically two to three times slower than a copy collector that successfully completes the garbage collection process with no abort.
In view of the foregoing, what is needed is a copy collector able to efficiently transition to a mark collector when an abort occurs. Ideally, if an abort does occur, the operation of the copy collector and mark collector together will be almost as fast and efficient as the copy collector completing by itself without an abort. If an abort does occur, techniques are needed to enable the mark collector to resume tracing work and reference updating already performed by the copy collector with minimal repetition of work.